package com.leetcode.day7_31;

import com.sun.corba.se.impl.resolver.SplitLocalResolverImpl;

import java.util.*;


/**
 * author: the_ring
 * Time: 2021/7/31 15:18
 * log: 二叉树的垂序遍历
 * link:https://leetcode-cn.com/problems/vertical-order-traversal-of-a-binary-tree/
 */

class Solution {

    // 方法来源于网络
    public static List<List<Integer>> verticalTraversal2(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> list = new ArrayList<>();
        Map<TreeNode,int[]> map = new HashMap<>();
        PriorityQueue<int[]> priorityQueue = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[1] == o2[1]) {
                    if (o1[0] == o2[0]) {
                        return o1[2] - o2[2];
                    } else {
                        return o1[0] - o2[0];
                    }
                } else {
                    return o1[1] - o2[1];
                }
            }
        });
        queue.offer(root);
        map.put(root,new int[]{0,0,root.val});
        priorityQueue.add(new int[]{0,0, root.val});
        int row = 0;
        while (!queue.isEmpty()) {
            row++;
            int size = queue.size();
            for (int i = 0;i < size;i++) {
                TreeNode temp = queue.poll();
                if (temp.left != null) {
                    queue.offer(temp.left);
                    int[] one = new int[]{row,map.get(temp)[1] - 1,temp.left.val};
                    map.put(temp.left,one);
                    priorityQueue.add(one);
                }
                if (temp.right != null) {
                    queue.offer(temp.right);
                    int[] two = new int[]{row,map.get(temp)[1] + 1,temp.right.val};
                    map.put(temp.right,two);
                    priorityQueue.add(two);
                }
            }
        }
        int pre = Integer.MIN_VALUE;
        while (!priorityQueue.isEmpty()) {
            int[] one = priorityQueue.poll();
            if (one[1] != pre) {
                List<Integer> subList = new ArrayList<>();
                pre = one[1];
                list.add(subList);
            }
            list.get(list.size() - 1).add(one[2]);
        }
        return list;
    }


    public static List<List<Integer>> verticalTraversal(TreeNode root) {
        // 先计算其有多少列
        int left = 0;
        int right = 0;
        TreeNode temp = root;
        while (temp.right != null) {
            temp = temp.right;
            right++;
        }
        temp = root;
        while (temp.left != null) {
            temp = temp.left;
            left++;
        }

        // 初始化
        List<List<Integer>> result = new ArrayList<>(left + right + 1);
        for (int i = 0; i < left + right + 1; i++) {
            List<Integer> column = new ArrayList<>();
            column.add(Integer.MAX_VALUE);
            result.add(column);
        }


//        Stack<Node> stack = new Stack<>();
//        stack.push(new Node(root, left));
//        while (!stack.empty()) {
//            Node node = stack.pop();
//            TreeNode tnode = node.getNode();
//            int position = node.getPosition();
//            result.get(node.getPosition()).add(tnode.val);
//            if (tnode.right != null) stack.push(new Node(tnode.right, position + 1));
//            if (tnode.left != null) stack.push(new Node(tnode.left, position - 1));
//        }

        // 使用队列
        Queue<Node> queue = new LinkedList<>();
        queue.add(new Node(root, left));
        while (!queue.isEmpty()) {
            Node node = queue.peek();
            TreeNode tnode = node.getNode();
            int position = node.getPosition();
            result.get(node.getPosition()).add(tnode.val);
            if (tnode.right != null) queue.add(new Node(tnode.right, position + 1));
            if (tnode.left != null) queue.add(new Node(tnode.left, position - 1));
        }

        for (List<Integer> list : result) {
            list.remove(0);
            Collections.sort(list);
        }
        return result;
    }


    public static void main(String[] args) {
        TreeNode tree = new TreeNode(1);
        tree.right = new TreeNode(3, new TreeNode(6), new TreeNode(7));
        tree.left = new TreeNode(2, new TreeNode(4), new TreeNode(5));
        List<List<Integer>> result = verticalTraversal2(tree);
        int i = 1;
        for (List<Integer> integers : result) {
            System.out.print(i + ": ");
            i++;
            for (Integer integer : integers) {
                System.out.print(integer + " ");
            }
            System.out.println();
        }
    }
}

class Node {
    private TreeNode node;
    private int position;

    public Node(TreeNode node, int position) {
        this.node = node;
        this.position = position;
    }

    public TreeNode getNode() {
        return node;
    }

    public void setNode(TreeNode node) {
        this.node = node;
    }

    public int getPosition() {
        return position;
    }

    public void setPosition(int position) {
        this.position = position;
    }
}


//  Definition for a binary tree node.
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}